<?php

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 * Description of JaroWinkler
 *
 * @author acer
 * Tested in 25.12.2011 15:14
 */
class JaroWinkler {
    //put your code here
    
    /**
     * Verilen iki stringin benzerlik oranını Jaro-Winkler algoritmasını kullanarak hesaplar.
     * Oluşan sonuç 0-1 arasındadır. 1'e yaklaştıkça benzerlik artar, aynı stringler için 1'dir.
     * @param string $source
     * @param string $target
     * @return float 
     */
    public function benzerlikOrani($source, $target) {
        $dist = $this->jaroBenzerlikOrani($source, $target);
        if($dist < 0 || $dist > 1) {
            throw new Exception("innerDistance should produce scores between 0 and 1");
        }
        $prefLength = self::commonPrefixLength(4, $source, $target);
        $dist = $dist + $prefLength * 0.1 * (1 - $dist);
        return $dist;
    }
    
    /**
     * 
     * @param string $source
     * @param string $target
     * @return float
     * @todo buradaki stringler için bir String sınıfı oluştur, lengthlerini direk çektir. 
     */
    private function jaroBenzerlikOrani($source, $target) {
        $halflen = $this->halfLengthOfShorter($source, $target);
        $common1 = $this->commonChars($source, $target, $halflen);
        $common2 = $this->commonChars($target, $source, $halflen);
        if(strlen($common1) != strlen($common2)) {
            return 0;
        }
        if(strlen($common1) == 0 && strlen($common2) == 0) {
            return 0;
        }
        $transpositions = $this->transpositions($common1, $common2);
        $dist = 
            (
            strlen($common1) / floatval(strlen($source)) +
            strlen($common2) / floatval(strlen($target)) +
            (strlen($common1) - $transpositions) / (floatval(strlen($common1)))
            ) / 3.0;
        return $dist;
    }
    
    /**
     *
     * @param string $source
     * @param string $target
     * @return int 
     */
    private function halfLengthOfShorter($source, $target) {
        return (strlen($source) > strlen($target)) ? (strlen($target) / 2) + 1 : (strlen($source) / 2) + 1;
    }
    
    /**
     *
     * @param string $s
     * @param string $t
     * @param int $halflen
     * @return string 
     */
    private function commonChars($s, $t, $halflen) {
        $common = "";
        $copy = substr($t, 0);
        for($i = 0; $i < strlen($s); $i++) {
            $ch = $s[$i];
            $foundIt = false;
            for($j = max(array(0, $i - $halflen)); !$foundIt && $j < min(array($i + $halflen, strlen($t))); $j++) {
                if($copy[$j] == $ch) {
                    $foundIt = true;
                    $common .= $ch;
                    $copy[$j] = "*";
                }
            }
        }
        return $common;
    }
    
    private function transpositions($common1, $common2) {
        $transpositions = 0;
        for($i = 0; $i < strlen($common1); $i++) {
            if($common1[$i] != $common2[$i]) {
                $transpositions++;
            }
        }
        $transpositions /= 2;
        return $transpositions;
    }
    
    /**
     *
     * @param int $maxLength
     * @param string $common1
     * @param string $common2
     * @return ınt 
     */
    private static function commonPrefixLength($maxLength, $common1, $common2) {
        $n = min(array(strlen($common1), strlen($common2)));
        for($i = 0; $i < $n; $i++) {
            if($common1[$i] != $common2[$i]) {
                return $i;
            }
        }
        return $n;
    }
}